/*
 * @Author: liusheng
 * @Date: 2022-04-18 22:24:22
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-19 15:49:08
 * @Description: 剑指 Offer II 033. 变位词组
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 
 剑指 Offer II 033. 变位词组
给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。

注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。

 

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:

输入: strs = [""]
输出: [[""]]
示例 3:

输入: strs = ["a"]
输出: [["a"]]
 

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
 

注意：本题与主站 49 题相同： https://leetcode-cn.com/problems/group-anagrams/
 */

#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>

using namespace std;

//sort solution
//sorted the string,then add into map
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int len = strs.size();
        vector<vector<string>> anagramGroup;
        unordered_map<string,int> anagramMap;
        for (int i = 0; i < len; ++i)
        {
            string sortedStr = strs[i];
            sort(sortedStr.begin(),sortedStr.end());
            if (anagramMap.count(sortedStr))
            {
                int anagramIndex = anagramMap[sortedStr];
                anagramGroup[anagramIndex].emplace_back(strs[i]);
            }
            else
            {
                //the sorted string as key,index as value
                anagramMap[sortedStr] = anagramGroup.size();

                vector<string> anagramStr;
                //place the origin string
                anagramStr.emplace_back(strs[i]);
                anagramGroup.emplace_back(anagramStr);
            }
        }
        return anagramGroup;
    }
};

//hash solution,unordered_map take array<int, 26> as key
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int len = strs.size();
        vector<vector<string>> anagramGroups;
        // 自定义对 array<int, 26> 类型的哈希函数
        auto arrayHash = [fn=hash<string>{}] (const array<int,26> & strCnt) ->size_t
        {
            string hashStr;
            for (int i = 0; i < 26; ++i)
            {
                if (strCnt[i])
                {
                    //hashStr push back the character
                    hashStr.push_back('a' + i);
                    //hashStr push back the character's appearance time
                    hashStr += to_string(strCnt[i]);
                } 
            }
            // printf("hashStr:%s,hashVal=%ld\n",hashStr.c_str(),fn(hashStr));
            return fn(hashStr);
        };
        
        unordered_map<array<int, 26>,int,decltype(arrayHash)> wordMap(0,arrayHash);//string count,index map
        array<int, 26> wordCount = {};//word statistics for every word
        for (int i = 0; i < len; ++i)
        {
            wordCount.fill(0);
            for (int j = 0; j < strs[i].size();++j)
            {
                ++wordCount[strs[i][j] - 'a'];
            }
            if (wordMap.count(wordCount))
            {
                int anagramIndex = wordMap[wordCount];
                anagramGroups[anagramIndex].emplace_back(strs[i]);
            }
            else
            {
                wordMap[wordCount] = anagramGroups.size();
                vector<string> anagramG;
                anagramG.emplace_back(strs[i]);
                anagramGroups.emplace_back(anagramG);
            }
        }

        return anagramGroups;
    }
};

//wrong solution,unordered_map as key of unordered_map,this can make sense by use the 
//overload hash function,but to this problem,the hash function product different hash 
//when process anagram string,so it's wrong
//
class WrongSolutionWithUnordered_map {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int len = strs.size();
        vector<vector<string>>  anagramGroups;
        if (!len)
        {
            return anagramGroups;
        }
        
        auto unorderedMapHash = [fn=hash<string>{}] (const unordered_map<char,char> & charCnt) ->size_t
        {
            string hashStr;

            for (auto cnt: charCnt)
            {
                hashStr += cnt.first;
                hashStr += to_string(cnt.second);
            }
            printf("hashStr:%s,hashVal=%ld\n",hashStr.c_str(),fn(hashStr));
            return fn(hashStr);
        };
        
        unordered_map<unordered_map<char,char>,char,decltype(unorderedMapHash)> wordMap(0,unorderedMapHash);
        unordered_map<char,char> wordCount;
        for (int i = 0; i < len; ++i)
        {
            wordCount.clear();
            for (char ch: strs[i])
            {
                ++wordCount[ch];
            }
            
            if (wordMap.count(wordCount))
            {
                int anagramIndex = wordMap[wordCount];
                anagramGroups[anagramIndex].emplace_back(strs[i]);
            }
            else
            {
                wordMap[wordCount] = anagramGroups.size();
                vector<string> anagramG = {strs[i]};
                anagramGroups.emplace_back(anagramG);
            }
        }
        
        return anagramGroups;
    }
};